1. Field of the Invention
The present invention relates to a garbage collection apparatus for performing scavenging and compaction on cells using trays.
2. Description of the Prior Art
An application uses a heap for performing dynamic memory allocation. The heap referred to as unused cells. The application reserves a number of cells required for an application process as a cell block.
FIG. 28 shows an example of a heap. In the drawing, the heap includes a root cell block, cell blocks 1 to 5, and an unused cell area. The unused cell area is a collection of unused cells that have not been allocated.
When reserving memory the application forms reference relationships between cell blocks so that a reserved cell block can be referenced by other cell blocks. In FIG. 28 such references are shown by polygonal lines. A cell block 4 is referenced by a root cell block, a cell block 2 by the cell block 4, and a cell block 5 by the cell block 2. The root cell block is a cell block that is the start of the reference relationship.
To explain in more detail, the application holds a valid reference showing a start cell of the reserved cell block in a cell included in another cell block. A valid reference is a cell address or similar. To give one example shown in FIG. 28, the application holds a valid reference 3 showing a start cell in a cell block 2.
However, cell blocks that cannot be traced (reached) from the root cell block may be generated when the application is executing processing for a particular process. Such cell blocks are said to be unreachable (dead). Processing performed to free unreachable cell blocks and collect the freed cell blocks together to form an unused cell area in which cell blocks are once more capable of being used is known as garbage collection. A device for executing this processing is known as a garbage collector.
The garbage collector performs scavenging (relocating unreachable objects) and compaction (also known as compactifying). In FIG. 28, the garbage collector performs scavenging to return unreachable cell blocks 1 and 3 to an unused state, and then performs compaction to gather up the plurality of unused cell blocks into one unused cell area. When this processing is performed, the garbage collector updates valid references held by cells in order to maintain reference relationships between cell blocks.
Various refinements have been made to the algorithm used by the garbage collector. The following is an explanation of three garbage collectors in the prior art.
FIG. 29 shows a structure of a heap in a first prior art. In the drawing, the heap includes cells, and reference flags corresponding to each cell. The garbage collector performs scavenging as follows:
(1) sets xe2x80x98in usexe2x80x99 flags indicating whether cell blocks are in use or not at 0 (here, an xe2x80x98in usexe2x80x99 flag uses 1 bit from each cell block);
(2) reads a valid reference held in a root cell block;
(3) determines that a cell block at a location indicated by the read valid reference is in use, and sets the xe2x80x98in usexe2x80x99 flag for the cell block at 1;
(4) refers successively to each of the reference flags for the cell block determined to be in use, and retrieves all of the reference flags set at 1; and
(5) reads valid references held in cells corresponding to each of the retrieved references. The garbage collector repeats the processing of (3) to (5) for all of the cell blocks that are reachable from the root cell block.
Following this, the garbage collector performs the following compaction:
(1) calculates a reference value for a start cell after compaction for all cell blocks with an xe2x80x98in usexe2x80x99 flag set at 1;
(2) rewrites reference values for all cells that have an xe2x80x98in usexe2x80x99 flag and a reference flag set at 1 with the reference values calculated in (1); and
(3) shifts cell blocks with an xe2x80x98in usexe2x80x99 flag set at 1 to the reference locations calculated in (1).
FIG. 30 shows a heap memory for a second prior art example. As shown in the drawing, the heaps includes reference flags, cells, and trays. A cell block holds a valid handle indicating a tray, and the tray holds a valid reference indicating a start cell in a cell block. Reference relationships between cell blocks are indicated indirectly by using trays.
For example, a cell block 4 holds a valid handle 1, which indicates a tray with a valid handle 1. The tray with the valid handle 1 holds a valid reference 3, which indicates a cell block 2 in which the valid reference 3 is located. Thus, cell block 3 can reference cell block 2.
The garbage collector in the second prior art performs the following scavenging:
(1) specifies, via trays, cell blocks that are reachable from the root cell block, and sets the xe2x80x98in usexe2x80x99 flags for these cell blocks at 1 (this processing is similar to that in the first prior art);
(2) changes valid references for trays which are not referenced by any cell block to NULL references.
As one example of (2), the garbage collector updates the content of a tray with a valid handle 0 and a tray with a valid handle 2 that are not referenced by any cell block to a NULL reference. A NULL reference indicates that a tray is unused. Thus, cell blocks 1 and 3, whose valid references 1 and 6 were held by the trays with the valid handles 0 and 2 prior to updating, are freed by the garbage collector to form an unused cell area.
Following this, the garbage collector in the second prior art performs compaction as follows:
(1) calculates a reference value for a start cell after compaction for all cell blocks with an xe2x80x98in usexe2x80x99 flag set at 1;
(2) overwrites trays holding a valid reference with the reference values calculated in (1); and
(3) shifts cell blocks with xe2x80x98in usexe2x80x99 flags set at 1 to a reference location calculated in (1).
In the example shown in FIG. 30, cell blocks 4 and 5 are shifted forward by an amount corresponding to the size of the freed cell blocks 1 and 3. Here, the garbage collector updates the content of the trays so as to maintain references from a root cell block to a cell block 4, and the cell block 4 to a cell block 2 and a cell block 5.
FIG. 31 shows a heap for a third prior art. The third prior art is one example of what is known as a conservative garbage collector. Such technology is disclosed in more detail in Garbage Collection in an Uncooperative Environment (Hans-Juergen Boehm and Mark Weiser, Software Practice and Experience Vol. 18, pub. September 1988, pages 807 to 820).
Here, the heap holds pointers (references) to cell blocks at a start of each cell block. The garbage collector in the third prior art performs the following scavenging:
(1) sets xe2x80x98in usexe2x80x99 flags indicating whether cell blocks are in use at 0;
(2) reads a valid reference held in the root cell block;
(3) determines whether a cell block at a location indicated by the read valid reference is in use;
(4) reads content at a start location of a cell block determined to be in use, and makes an assumption as to whether the read content is a reference value.
The garbage collector repeats the above processing (3) to (4) for all cell blocks that are reachable from the root cell block.
In FIG. 31, the polygonal lines show reference relationships between cell blocks.
The garbage collector in the third prior art makes assumptions as to whether cells contain numerical values or references, and performs garbage collection in accordance with the results of these assumptions. However, the garbage collector may mistakenly assume that a numerical value is a reference. For example, in FIG. 31, the garbage collector mistakenly assumes that a numerical value 6 is a valid reference. The curved line in the drawing shows the referencing that is performed based on this mistaken assumption. Since the garbage collector mistakenly assumes the numerical value 6 to be a valid handle 6, a mistaken reference from cell block 2 to cell block 3 is produced.
The garbage collector in the third prior art can perform scavenging, but not compaction. The reason for this is that if compaction is performed when such mistaken assumptions have been made, numerical values which have been mistakenly assumed to be handles will be updated.
As explained above, the garbage collectors in the first and second prior arts perform scavenging and compaction, and the garbage collector in the third prior art performs scavenging alone, to keep the heap in a state such that memory of a size required by the application can be reserved.
However, since the garbage collectors in the first and second prior arts use reference flags, reference flags are set while an application is being executed. Consequently, the processing load placed on the processor is increased, and the time required to execute the application is longer than that for an application that does not perform garbage collection.
Moreover, the garbage collector of the second prior art performs compaction at high speed, but, since handles are used, a larger amount of memory needs to be reserved than for the first prior art.
The garbage collector of the third prior art does not use reference flags when the application is executed, and so the processing load during execution of the application is lower than for the garbage collector of the first and second prior arts. However, the garbage collector of the third prior art does not perform compaction since numerical values may have been mistakenly assumed to be references. When compaction is not performed, the unused area is fragmented, and the number of small areas that cannot be recycled increases.
The present invention may be realized by a garbage collection apparatus that performs (1) scavenging processing for specifying unused cell blocks from among a plurality of cell blocks, some of which can be reached from a specified root cell block via one of a set of trays, tracing one or more cell blocks in a chain-like manner by referencing each of the one or more cell blocks, and others of which cannot be reached in this manner and are referred to as the unused cell blocks, each of the set of trays being specified by a second type address and holding a first type address, each of the plurality of cell blocks (a) being specified by a first type address and (b) including a plurality of cells that each hold one of a second type address and a numerical value, and (2) compaction processing for relocating each of the specified unused cell blocks so as to form a continuous memory area, and updating each first type address that is held in a tray and corresponds to a cell block so as to specify a cell block following relocation, the garbage collection apparatus comprising: assuming means for making an assumption as to whether a second type address is stored in a cell included in a first cell block, so as to avoid a situation in which the second type address is mistakenly assumed not to be a second type address; and specifying means for specifying an unused cell block using the scavenging processing by assuming that a second cell block is referenced by the first cell block, the second cell block being specified by a first type address, the first type address being held in a tray specified by data held in the cell that is assumed to be holding the second type address.
This enables the garbage collection apparatus to use trays to specify cells, and update first type addresses held in trays when performing compaction. Since the actual content of a cell is not updated, effective high-speed compaction can be achieved. Furthermore, the garbage collection apparatus does not use reference flags or similar to exchange information with an application when scavenging and compaction are performed. As a result, there is no need to reserve memory for reference flags, and an excessive processing load is not generated when executing an application that uses cells.
Furthermore, in the above garbage collection apparatus, a tray indicating an unused cell block newly specified by the scavenging processing may be recognized as an unused tray that does not hold a first type address.
In addition to the above effects, this construction enables the garbage collection apparatus to recycle trays which no longer need to be used, when a new request for use of cells is received.
Furthermore, in the above garbage collection apparatus, a value used for the second type address may be limited to within a specific range, the assuming means makes the assumption that data held by a cell is a second type address only when a tray, indicated when (1) the data is within the specific range and (2) the data is hypothetically assumed to be a type two address, is not an unused tray, and the garbage collection apparatus further comprises: detecting means for detecting that a value has been newly assigned to a cell; and prohibiting means for prohibiting, when the newly assigned value is assumed to be a second type address by the assuming means, use of a tray specified by the numerical value by hypothetically assuming that the value is a second type address.
In addition to the above effects, the garbage collection apparatus having this construction prohibits use of trays corresponding to numerical values which have been newly assigned to a cell, and judges whether a tray specified by the data assigned to a cell is an unused tray when an assumption is made. Consequently, cases in which a numerical value within the specified range for second type addresses is mistakenly assumed to be a second type address can be avoided.
Furthermore, the above garbage collection apparatus may further comprise: freeing means for freeing, when (1) a specified number of trays that each (a) hold a first type address or (b) are prohibited from being used, cannot be used, and (2) a request for use of a new tray is received, the trays that are prohibited from being used.
The garbage collection apparatus with this construction, in addition to the above effects, enables trays, about which mistaken assumptions are likely to be made, but which are no longer in use, to be recycled effectively.